#include "QuickSortRandom.h"

template<typename T>
T _OrderSelect(T* vec, size_t startPos, size_t endPos , size_t selectPos)
{
	if(startPos==endPos)
		return vec[endPos];
	size_t middle = PartitionRandom(vec,startPos,endPos);
	if(middle==selectPos)
		return vec[middle];
	else if(selectPos < middle)
		return _OrderSelect(vec,startPos,middle-1,selectPos);
	else
		return _OrderSelect(vec,middle+1,endPos,selectPos);
}

template<typename T>
T OrderSelect(T* vec, size_t cnt , size_t selectPos)
{
	if(selectPos<=0 || selectPos>cnt)
	{
		printf("Error: the select pos must in the range [1,cnt]\n");
		exit(1);
	}
	T *p=new T[cnt];
	for(size_t i=0;i<cnt;++i)
		p[i]=vec[i];
	T temp=_OrderSelect(p, 0, cnt-1 , selectPos-1);
	delete []p;
	return temp;
}

